package com.dycong.common.leetcode.ds.tree;

import org.junit.Test;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * @author dycong
 * @date 2019/8/1 8:41
 */
public class TreeTraverse {

    /*
        1
   / \
  2   3
 / \   \
4   5   6
层次遍历顺序：[1 2 3 4 5 6]
前序遍历顺序：[1 2 4 5 3 6]
中序遍历顺序：[4 2 5 1 3 6]
后序遍历顺序：[4 5 2 6 3 1]
层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。

层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。

前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。

① 前序

    void dfs(TreeNode root) {
        visit(root);
        dfs(root.left);
        dfs(root.right);
    }

② 中序

    void dfs(TreeNode root) {
        dfs(root.left);
        visit(root);
        dfs(root.right);
    }

 ③ 后序

    void dfs(TreeNode root) {
        dfs(root.left);
        dfs(root.right);
        visit(root);
    }
     */


    /**
     * 前序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> preOrderTraversal(com.dycong.common.leetcode.ds.tree.TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<com.dycong.common.leetcode.ds.tree.TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            com.dycong.common.leetcode.ds.tree.TreeNode node = stack.pop();
            if (node == null) continue;
            ret.add(node.val);
            stack.push(node.right);  // 先右后左，保证左子树先遍历
            stack.push(node.left);
        }
        return ret;
    }


    /**
     * 后序遍历
     * 前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。
     */

    public List<Integer> postOrderTraversal(com.dycong.common.leetcode.ds.tree.TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<com.dycong.common.leetcode.ds.tree.TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            com.dycong.common.leetcode.ds.tree.TreeNode node = stack.pop();
            if (node == null) continue;
            ret.add(node.val);
            stack.push(node.left);
            stack.push(node.right);
        }
        Collections.reverse(ret);
        return ret;
    }

    /**
     * 中序遍历
     */
    public List<Integer> inOrderTraversal(com.dycong.common.leetcode.ds.tree.TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Stack<com.dycong.common.leetcode.ds.tree.TreeNode> stack = new Stack<>();
        com.dycong.common.leetcode.ds.tree.TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            com.dycong.common.leetcode.ds.tree.TreeNode node = stack.pop();
            ret.add(node.val);
            cur = node.right;
        }
        return ret;
    }


    /**
     * 层序遍历
     * BFS
     */
    public List<Integer> sequenceTraversal(com.dycong.common.leetcode.ds.tree.TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;

        Queue<com.dycong.common.leetcode.ds.tree.TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            com.dycong.common.leetcode.ds.tree.TreeNode node = queue.poll();
            //process node
            ret.add(node.val);
            //generate related nodes
            com.dycong.common.leetcode.ds.tree.TreeNode left = node.left;
            com.dycong.common.leetcode.ds.tree.TreeNode right = node.right;
            if (left != null)
                queue.add(node.left);
            if (right != null)
                queue.add(node.right);
        }
        return ret;
    }


    /**
     * BFS 图 有循环指向 需要判重
     */
    public List<Integer> bfs2Traversal(com.dycong.common.leetcode.ds.tree.TreeNode root) {
        List<Integer> ret = new ArrayList<>();

        //当 BFS 对象是图时需要做判重，判断节点是否访问多，二叉树不需要
        Set<com.dycong.common.leetcode.ds.tree.TreeNode> visited = new HashSet<>();

        if (root == null) return ret;
        Queue<com.dycong.common.leetcode.ds.tree.TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);
        visited.add(root);
        while (!queue.isEmpty()) {
            com.dycong.common.leetcode.ds.tree.TreeNode node = queue.poll();
            visited.add(node);
            //process node
            ret.add(node.val);

            //generate related nodes and judge repetition
            com.dycong.common.leetcode.ds.tree.TreeNode left = node.left;
            if (left != null && !visited.contains(left)) {
                queue.add(left);
            }

            com.dycong.common.leetcode.ds.tree.TreeNode right = node.right;
            if (right != null && !visited.contains(right)) {
                queue.add(right);
            }
        }
        return ret;
    }


    /**
     * 递归前序遍历
     *
     * @param root
     * @param ret
     * @return
     */
    public List<Integer> preOrder(com.dycong.common.leetcode.ds.tree.TreeNode root, List<Integer> ret) {
        if (root == null) return ret;
        ret.add(root.val);
        preOrder(root.left, ret);
        preOrder(root.right, ret);
        return ret;
    }

    /**
     * 递归中序遍历
     *
     * @param root
     * @param ret
     * @return
     */
    public List<Integer> inOrder(com.dycong.common.leetcode.ds.tree.TreeNode root, List<Integer> ret) {
        if (root == null) return ret;

        inOrder(root.left, ret);
        ret.add(root.val);
        inOrder(root.right, ret);
        return ret;
    }

    /**
     * 递归后序遍历
     *
     * @param root
     * @param ret
     * @return
     */
    public List<Integer> postOrder(com.dycong.common.leetcode.ds.tree.TreeNode root, List<Integer> ret) {
        if (root == null) return ret;

        postOrder(root.left, ret);
        postOrder(root.right, ret);
        ret.add(root.val);
        return ret;
    }


    @Test
    public void test() {
        List<Integer> preOrderTraversal = preOrderTraversal(getTree());
        System.out.println(preOrderTraversal);
        List<Integer> inOrderTraversal = inOrderTraversal(getTree());
        System.out.println(inOrderTraversal);
        List<Integer> postOrderTraversal = postOrderTraversal(getTree());
        System.out.println(postOrderTraversal);
        List<Integer> sequenceTraversal = sequenceTraversal(getTree());
        System.out.println(sequenceTraversal);
    }

    public com.dycong.common.leetcode.ds.tree.TreeNode getTree() {
        TreeHelper treeHelper = new TreeHelper();
        return treeHelper.getTree(5);
    }

    public static class TreeHelper {
        private int index = 0;

        private int incrementAndGet() {
            return ++index;
        }

        public com.dycong.common.leetcode.ds.tree.TreeNode getTree(int max) {
            int i = 1;
            com.dycong.common.leetcode.ds.tree.TreeNode root = new com.dycong.common.leetcode.ds.tree.TreeNode(incrementAndGet());
            process(root, i, max);
            return root;
        }

        private void process(com.dycong.common.leetcode.ds.tree.TreeNode root, int start, int max) {
            if (null == root) return;
            if (start >= max) return;
            start++;
            com.dycong.common.leetcode.ds.tree.TreeNode left = new com.dycong.common.leetcode.ds.tree.TreeNode(incrementAndGet());
            com.dycong.common.leetcode.ds.tree.TreeNode right = new TreeNode(incrementAndGet());
            root.left = left;
            root.right = right;
            process(left, start, max);
            process(right, start, max);
        }
    }
}
